package main.剑指OfferⅠ;

public class Day9 {
    public static void main(String[] args) {
        System.out.println("剑指Offer42.连续子数组的最大和");
        System.out.println("剑指Offer47.礼物的最大价值");
    }
}

class Offer42{
    public int maxSubArray(int[] nums) {
        int length= nums.length,max=Integer.MIN_VALUE;
        int[] dp=new int[length];
        for (int i=0;i<length;i++){
            if (i==0) dp[i]=nums[i];
            else if (dp[i-1]>0) dp[i]=dp[i-1]+nums[i];
            else dp[i]=nums[i];
            max=Math.max(max,dp[i]);
        }
        return max;
    }
}

class Offer47{
    public int maxValue(int[][] grid) {
        int m= grid.length,n=grid[0].length;
        int[][] dp=new int[m][n];
        for (int i=0;i<m;i++){
            for (int j=0;j<n;j++){
                if (i==0&&j==0) {
                    dp[i][j]=grid[i][j];
                    continue;
                }
                if (i==0) dp[i][j]=grid[i][j]+dp[i][j-1];
                else if (j==0) dp[i][j]=grid[i][j]+dp[i-1][j];
                else dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1])+grid[i][j];
            }
        }
        return dp[m-1][n-1];
    }
}